package tasks.zhuanyeji.npu最小峰值占用;


import java.util.Arrays;

public class NPU最小峰值占用 {

    /**
     * 计算NPU最小峰值占用
     *
     * @param loads 每个任务的计算负载数组
     * @param m     需要划分的批次数
     * @return 最小可能的峰值占用
     */
    public int minPeakLoad(int[] loads, int m) {
        if (loads == null || loads.length == 0) {
            return 0;
        }
        if (loads.length < m) {
            return 0;
        }

        int left = 0;
        int right = 0;
        for (int load : loads) {
            left = Math.max(load, left);
            right += load;
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canSplit(loads, m, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canSplit(int[] loads, int m, int mid) {
        int currentBathCount = 0;
        int count = 1;
        for (int load : loads) {
            if (currentBathCount + load > mid) {
                currentBathCount = load;
                count++;
                if (count > m) {
                    return false;
                }
            } else {
                currentBathCount += load;
            }
        }
        return true;
    }

    // 测试用例
    public static void main(String[] args) {
        NPU最小峰值占用 solution = new NPU最小峰值占用();

        // 示例3
        int[] loads3 = {10, 5, 13, 4, 8, 7, 3};
        int m3 = 3;
        System.out.println("\n示例3 - 输入: " + Arrays.toString(loads3) + ", m = " + m3);
        System.out.println("输出: " + solution.minPeakLoad(loads3, m3)); // 期望输出: 17
    }
}
